if (!require("BiocManager", quietly = TRUE))
    install.packages("BiocManager")

BiocManager::install("curatedTCGAData");
Update all/some/none? [a/s/n]: 
n
BiocManager::install("TCGAutils");
Update all/some/none? [a/s/n]: 
n
BiocManager::install("TCGAbiolinks");
Update all/some/none? [a/s/n]: 
n

install.packages("SNFtool");
Error in install.packages : Updating loaded packages
install.packages("NetPreProc");
Error in install.packages : Updating loaded packages
library("curatedTCGAData");
library("TCGAbiolinks");
library("TCGAutils");

library("SNFtool")
library("NetPreProc");
library("cluster");

1 Download Prostate adenocarcinoma dataset


assays <- c("miRNASeqGene", "RNASeq2Gene", "RPPAArray");
mo <- curatedTCGAData(diseaseCode = "PRAD", 
                        assays = assays,
                        version = "2.1.1", dry.run=FALSE);
snapshotDate(): 2023-10-24
Working on: PRAD_RNASeq2Gene-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_RPPAArray-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_miRNASeqGene-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_colData-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_sampleMap-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_metadata-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
harmonizing input:
  removing 5189 sampleMap rows not in names(experiments)
mo
A MultiAssayExperiment object of 3 listed
 experiments with user-defined names and respective classes.
 Containing an ExperimentList class object of length 3:
 [1] PRAD_RNASeq2Gene-20160128: SummarizedExperiment with 20501 rows and 550 columns
 [2] PRAD_RPPAArray-20160128: SummarizedExperiment with 195 rows and 352 columns
 [3] PRAD_miRNASeqGene-20160128: SummarizedExperiment with 1046 rows and 547 columns
Functionality:
 experiments() - obtain the ExperimentList instance
 colData() - the primary/phenotype DataFrame
 sampleMap() - the sample coordination DataFrame
 `$`, `[`, `[[` - extract colData columns, subset, or experiment
 *Format() - convert into a long or wide DataFrame
 assays() - convert ExperimentList to a SimpleList of matrices
 exportClass() - save data to flat files

2 Data pre-processing

Consider only primary solid tumors Analyte information missing from PRAD_RPPAArray (20th position) that causes inconsistent barcode lengths in MultiArrayExperiment object mo (but doesn’t cause problems for the code below).

primary <- TCGAutils::TCGAsampleSelect(colnames(mo), c("01"));
mo <- mo[,primary,]

Check for replicates for same patient (first 12 characters) No replicates present in mo.

check_rep <- anyReplicated(mo);
print(check_rep)
 PRAD_RNASeq2Gene-20160128    PRAD_RPPAArray-20160128 PRAD_miRNASeqGene-20160128 
                     FALSE                      FALSE                      FALSE 

Remove FFPE samples (frozen tissue is better preseved)

no_ffpe <- which(as.data.frame(colData(mo))$patient.samples.sample.is_ffpe == "no");
as.data.frame(colData(mo))
mo <- mo[, no_ffpe, ];

Consider samples having all considered omics data

complete <- intersectColumns(mo);

ExpressionList → simple list of matrices

complete <- assays(complete)
print(dim(complete[[1]]))
[1] 20501   348

Transpose all three matrices, obtaining samples \(\times\) features

complete <- lapply(complete,FUN=t)

Remove features having missing values (no missing values in the current dataset)

for (i in 1:length(complete)){
  #print(dim(complete[[i]]))
  complete[[i]] <- complete[[i]][,colSums(is.na(complete[[i]]))==0]
  #print(dim(complete[[i]]))
}

Select features having more variance across samples because they bring more information.

nf <- 100;
for(i in 1:length(complete)){
    
    idx <- caret::nearZeroVar(complete[[i]])
    message(paste("Removed ", length(idx), "features from", names(complete)[i]));
    if(length(idx) != 0){
        complete[[i]] <- complete[[i]][, -idx];
    }

    if(ncol(complete[[i]]) <= nf) next
    
    vars <- apply(complete[[i]], 2, var);
    idx <- sort(vars, index.return=TRUE, decreasing = TRUE)$ix;
    
    complete[[i]] <- complete[[i]][, idx[1:nf]];
    
}
Removed  1334 features from PRAD_RNASeq2Gene-20160128
Removed  0 features from PRAD_RPPAArray-20160128
Removed  471 features from PRAD_miRNASeqGene-20160128

Standardize features with z-score

zscore <- function(data){
    
    zscore_vec <- function(x) { return ((x - mean(x)) / sd(x))}
    data <- apply(data, 2, zscore_vec)
    
    
    return(data)
}

complete <- lapply(complete, zscore);

Clean barcodes retaining only “Project-TSS-Participant” (first 12 characters)

for(v in 1:length(complete)){
    rownames(complete[[v]]) <- substr(rownames(complete[[v]]), 1, 12);
}

3 Download disease subtypes

subtypes <- as.data.frame(TCGAbiolinks::PanCancerAtlas_subtypes())

subtypes <- subtypes[subtypes$cancer.type == "PRAD", ];
# Retain only primary solid tumors and select samples in common with omics data
# (in the same order):
subtypes <- subtypes[TCGAutils::TCGAsampleSelect(subtypes$pan.samplesID, "01"), ];
sub_select <- substr(subtypes$pan.samplesID,1,12) %in% rownames(complete[[1]]);
subtypes <- subtypes[sub_select, ];

We consider only samples in the omics data in complete for which also subtype data is present in subtypes

rownames(subtypes) <- substr(subtypes$pan.samplesID, 1, 12);
for (i in 1:length(complete))
  complete[[i]] <- complete[[i]][rownames(subtypes),]
# Print number of samples for each subtype:
table(subtypes$Subtype_Integrative);

  1   2   3 
 60  83 105 

3.1 Check subtype & omics data order

count <- 0
for(i in 1:length(rownames(subtypes))){
  if(rownames(subtypes)[i] != rownames(complete[[1]])[i])
     count <- count + 1
}
count
[1] 0

All patients/samples are in the same order in both the datasets. # Multi-omics data integration Similarity matrices for each data source using exponential euclidian distance (affinity matrix).

3.2 Integration through SNF

Integration of the matrices using Similarity Network Fusion t number of iterations _K_ number of neighbours to consider to compute local similarity matrix

3.3 Integration through average

Integration through average of matrices

for (i in 1:length(W_list))
    plot(W_list[[i]],xlim=c(0,0.01),ylim=c(0,0.01))

4 Disease subtype discovery with PAM

Number of clusters.

4.1 Each data source

Convert similarity matrix into a distance matrix. The similarities are normalized in the range &$ using min-max normalization before conversion into distances.

# Convert similarity matrix into a distance matrix. The similarities
# are normalized in the range [0, 1] using min-max normalization before
# conversion into distances.
dist <- list()
D <- list()
for (i in 1:length((W_list))){
  dist[[i]] <- 1 - NetPreProc::Max.Min.norm(W_list[[i]])
  D[[i]] <- as.dist(dist[[i]])
}
for (i in 1:length((W_list)))
  pam.res <- pam(D[[i]], k=k)

4.2 Integrated data through mean

dist_mean <- 1 - NetPreProc::Max.Min.norm(W_int_mean);
D_mean <- as.dist(dist_mean); 

pam.res <- pam(D_mean, k=k);

4.3 Integrated data through SNF

dist_SNF <- 1 - NetPreProc::Max.Min.norm(W_int_SNF);
D_SNF <- as.dist(dist_SNF); 

# Apply clustering algorithms on integrated matrix:
pam.res <- pam(D_SNF, k=k);

#Disease subtype discovery with spectral clustering (Consider distance matrix calculated above) ## Integrated data through SNF

k <- length(unique(subtypes$Subtype_Integrative));
sc.res <- SNFtool::spectralClustering(W_int_SNF, K=k)
#to have uniform type
pam.sc.res <- pam(sc.res,k=k)
sessionInfo()
LS0tDQp0aXRsZTogIkJpb2luZm9ybWF0aWNzIHByb2plY3QgeWVhciAyMDIzLzIwMjQiDQphdXRob3I6ICJMdWNpYSBBbm5hIE1lbGxpbmkiDQpkYXRlOg0KI2JpYmxpb2dyYXBoeTogcmVmZXJlbmNlcy5iaWINCm91dHB1dDogDQogICAgaHRtbF9ub3RlYm9vazoNCiAgICAgICAgdG9jOiB0cnVlDQogICAgICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQ0KICAgICAgICB0b2NfZmxvYXQ6IHRydWUNCiAgICAgICAgdGhlbWU6IGNlcnVsZWFuDQogICAgICAgIGZpZ19jYXB0aW9uOiB0cnVlDQotLS0NCg0KDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KaWYgKCFyZXF1aXJlKCJCaW9jTWFuYWdlciIsIHF1aWV0bHkgPSBUUlVFKSkNCiAgICBpbnN0YWxsLnBhY2thZ2VzKCJCaW9jTWFuYWdlciIpDQoNCkJpb2NNYW5hZ2VyOjppbnN0YWxsKCJjdXJhdGVkVENHQURhdGEiKTsNCkJpb2NNYW5hZ2VyOjppbnN0YWxsKCJUQ0dBdXRpbHMiKTsNCkJpb2NNYW5hZ2VyOjppbnN0YWxsKCJUQ0dBYmlvbGlua3MiKTsNCg0KaW5zdGFsbC5wYWNrYWdlcygiU05GdG9vbCIpOw0KaW5zdGFsbC5wYWNrYWdlcygiTmV0UHJlUHJvYyIpOw0KYGBgDQoNCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpsaWJyYXJ5KCJjdXJhdGVkVENHQURhdGEiKTsNCmxpYnJhcnkoIlRDR0FiaW9saW5rcyIpOw0KbGlicmFyeSgiVENHQXV0aWxzIik7DQoNCmxpYnJhcnkoIlNORnRvb2wiKQ0KbGlicmFyeSgiTmV0UHJlUHJvYyIpOw0KbGlicmFyeSgiY2x1c3RlciIpOw0KYGBgDQojIERvd25sb2FkIFByb3N0YXRlIGFkZW5vY2FyY2lub21hIGRhdGFzZXQjDQo8IS0tIG1pUk5BU2VxR2VuZSAgICAgICAgICAgICAgR2VuZS1sZXZlbCBsb2cyIFJQTSBtaVJOQSBleHByZXNzaW9uIHZhbHVlcw0KPD5STkFTZXEyR2VuZSAgICAgICAgICAgICAgIFJTRU0gVFBNIGdlbmUgZXhwcmVzc2lvbiB2YWx1ZXMNCjw+UlBQQUFycmF5ICAgICAgICAgICAgICAgICBSZXZlcnNlIFBoYXNlIFByb3RlaW4gQXJyYXkgbm9ybWFsaXplZCBwcm90ZWluIGV4cHJlc3Npb24gdmFsdWVzIC0tPg0KYGBge3J9DQoNCmFzc2F5cyA8LSBjKCJtaVJOQVNlcUdlbmUiLCAiUk5BU2VxMkdlbmUiLCAiUlBQQUFycmF5Iik7DQptbyA8LSBjdXJhdGVkVENHQURhdGEoZGlzZWFzZUNvZGUgPSAiUFJBRCIsIA0KICAgICAgICAgICAgICAgICAgICAgICAgYXNzYXlzID0gYXNzYXlzLA0KICAgICAgICAgICAgICAgICAgICAgICAgdmVyc2lvbiA9ICIyLjEuMSIsIGRyeS5ydW49RkFMU0UpOw0KYGBgDQoNCmBgYHtyIG1lc3NhZ2U9VFJVRX0NCm1vDQpgYGANCiMgRGF0YSBwcmUtcHJvY2Vzc2luZw0KQ29uc2lkZXIgb25seSBwcmltYXJ5IHNvbGlkIHR1bW9ycw0KQW5hbHl0ZSBpbmZvcm1hdGlvbiBtaXNzaW5nIGZyb20gUFJBRF9SUFBBQXJyYXkgKDIwdGggcG9zaXRpb24pIHRoYXQgY2F1c2VzIGluY29uc2lzdGVudCBiYXJjb2RlIGxlbmd0aHMgaW4gTXVsdGlBcnJheUV4cGVyaW1lbnQgb2JqZWN0ICBgYGBtb2BgYCAoYnV0IGRvZXNuJ3QgY2F1c2UgcHJvYmxlbXMgZm9yIHRoZSBjb2RlIGJlbG93KS4NCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpwcmltYXJ5IDwtIFRDR0F1dGlsczo6VENHQXNhbXBsZVNlbGVjdChjb2xuYW1lcyhtbyksIGMoIjAxIikpOw0KbW8gPC0gbW9bLHByaW1hcnksXQ0KYGBgDQpDaGVjayBmb3IgcmVwbGljYXRlcyBmb3Igc2FtZSBwYXRpZW50IChmaXJzdCAxMiBjaGFyYWN0ZXJzKQ0KTm8gcmVwbGljYXRlcyBwcmVzZW50IGluIGBgYG1vYGBgLg0KYGBge3J9DQpjaGVja19yZXAgPC0gYW55UmVwbGljYXRlZChtbyk7DQpwcmludChjaGVja19yZXApDQpgYGANClJlbW92ZSBGRlBFIHNhbXBsZXMgKGZyb3plbiB0aXNzdWUgaXMgYmV0dGVyIHByZXNldmVkKQ0KYGBge3J9DQpub19mZnBlIDwtIHdoaWNoKGFzLmRhdGEuZnJhbWUoY29sRGF0YShtbykpJHBhdGllbnQuc2FtcGxlcy5zYW1wbGUuaXNfZmZwZSA9PSAibm8iKTsNCmFzLmRhdGEuZnJhbWUoY29sRGF0YShtbykpDQptbyA8LSBtb1ssIG5vX2ZmcGUsIF07DQpgYGANCkNvbnNpZGVyIHNhbXBsZXMgaGF2aW5nIGFsbCBjb25zaWRlcmVkIG9taWNzIGRhdGENCmBgYHtyfQ0KY29tcGxldGUgPC0gaW50ZXJzZWN0Q29sdW1ucyhtbyk7DQpgYGANCkV4cHJlc3Npb25MaXN0IOKGkiBzaW1wbGUgbGlzdCBvZiBtYXRyaWNlcw0KYGBge3J9DQpjb21wbGV0ZSA8LSBhc3NheXMoY29tcGxldGUpDQpwcmludChkaW0oY29tcGxldGVbWzFdXSkpDQpgYGANClRyYW5zcG9zZSBhbGwgdGhyZWUgbWF0cmljZXMsIG9idGFpbmluZyBzYW1wbGVzICRcdGltZXMkIGZlYXR1cmVzDQpgYGB7cn0NCmNvbXBsZXRlIDwtIGxhcHBseShjb21wbGV0ZSxGVU49dCkNCmBgYA0KUmVtb3ZlIGZlYXR1cmVzIGhhdmluZyBtaXNzaW5nIHZhbHVlcyAobm8gbWlzc2luZyB2YWx1ZXMgaW4gdGhlIGN1cnJlbnQgZGF0YXNldCkNCmBgYHtyfQ0KZm9yIChpIGluIDE6bGVuZ3RoKGNvbXBsZXRlKSl7DQogICNwcmludChkaW0oY29tcGxldGVbW2ldXSkpDQogIGNvbXBsZXRlW1tpXV0gPC0gY29tcGxldGVbW2ldXVssY29sU3Vtcyhpcy5uYShjb21wbGV0ZVtbaV1dKSk9PTBdDQogICNwcmludChkaW0oY29tcGxldGVbW2ldXSkpDQp9DQpgYGANClNlbGVjdCBmZWF0dXJlcyBoYXZpbmcgbW9yZSB2YXJpYW5jZSBhY3Jvc3Mgc2FtcGxlcyBiZWNhdXNlIHRoZXkgYnJpbmcgbW9yZSBpbmZvcm1hdGlvbi4NCmBgYHtyfQ0KbmYgPC0gMTAwOw0KZm9yKGkgaW4gMTpsZW5ndGgoY29tcGxldGUpKXsNCiAgICANCiAgICBpZHggPC0gY2FyZXQ6Om5lYXJaZXJvVmFyKGNvbXBsZXRlW1tpXV0pDQogICAgbWVzc2FnZShwYXN0ZSgiUmVtb3ZlZCAiLCBsZW5ndGgoaWR4KSwgImZlYXR1cmVzIGZyb20iLCBuYW1lcyhjb21wbGV0ZSlbaV0pKTsNCiAgICBpZihsZW5ndGgoaWR4KSAhPSAwKXsNCiAgICAgICAgY29tcGxldGVbW2ldXSA8LSBjb21wbGV0ZVtbaV1dWywgLWlkeF07DQogICAgfQ0KDQogICAgaWYobmNvbChjb21wbGV0ZVtbaV1dKSA8PSBuZikgbmV4dA0KICAgIA0KICAgIHZhcnMgPC0gYXBwbHkoY29tcGxldGVbW2ldXSwgMiwgdmFyKTsNCiAgICBpZHggPC0gc29ydCh2YXJzLCBpbmRleC5yZXR1cm49VFJVRSwgZGVjcmVhc2luZyA9IFRSVUUpJGl4Ow0KICAgIA0KICAgIGNvbXBsZXRlW1tpXV0gPC0gY29tcGxldGVbW2ldXVssIGlkeFsxOm5mXV07DQogICAgDQp9DQpgYGANCg0KU3RhbmRhcmRpemUgZmVhdHVyZXMgd2l0aCB6LXNjb3JlDQpgYGB7cn0NCnpzY29yZSA8LSBmdW5jdGlvbihkYXRhKXsNCiAgICANCiAgICB6c2NvcmVfdmVjIDwtIGZ1bmN0aW9uKHgpIHsgcmV0dXJuICgoeCAtIG1lYW4oeCkpIC8gc2QoeCkpfQ0KICAgIGRhdGEgPC0gYXBwbHkoZGF0YSwgMiwgenNjb3JlX3ZlYykNCiAgICANCiAgICANCiAgICByZXR1cm4oZGF0YSkNCn0NCg0KY29tcGxldGUgPC0gbGFwcGx5KGNvbXBsZXRlLCB6c2NvcmUpOw0KYGBgDQpDbGVhbiBiYXJjb2RlcyByZXRhaW5pbmcgb25seSAiUHJvamVjdC1UU1MtUGFydGljaXBhbnQiIChmaXJzdCAxMiBjaGFyYWN0ZXJzKQ0KYGBge3J9DQpmb3IodiBpbiAxOmxlbmd0aChjb21wbGV0ZSkpew0KICAgIHJvd25hbWVzKGNvbXBsZXRlW1t2XV0pIDwtIHN1YnN0cihyb3duYW1lcyhjb21wbGV0ZVtbdl1dKSwgMSwgMTIpOw0KfQ0KYGBgDQojIERvd25sb2FkIGRpc2Vhc2Ugc3VidHlwZXMNCmBgYHtyfQ0Kc3VidHlwZXMgPC0gYXMuZGF0YS5mcmFtZShUQ0dBYmlvbGlua3M6OlBhbkNhbmNlckF0bGFzX3N1YnR5cGVzKCkpDQoNCnN1YnR5cGVzIDwtIHN1YnR5cGVzW3N1YnR5cGVzJGNhbmNlci50eXBlID09ICJQUkFEIiwgXTsNCiMgUmV0YWluIG9ubHkgcHJpbWFyeSBzb2xpZCB0dW1vcnMgYW5kIHNlbGVjdCBzYW1wbGVzIGluIGNvbW1vbiB3aXRoIG9taWNzIGRhdGENCiMgKGluIHRoZSBzYW1lIG9yZGVyKToNCnN1YnR5cGVzIDwtIHN1YnR5cGVzW1RDR0F1dGlsczo6VENHQXNhbXBsZVNlbGVjdChzdWJ0eXBlcyRwYW4uc2FtcGxlc0lELCAiMDEiKSwgXTsNCnN1Yl9zZWxlY3QgPC0gc3Vic3RyKHN1YnR5cGVzJHBhbi5zYW1wbGVzSUQsMSwxMikgJWluJSByb3duYW1lcyhjb21wbGV0ZVtbMV1dKTsNCnN1YnR5cGVzIDwtIHN1YnR5cGVzW3N1Yl9zZWxlY3QsIF07DQpgYGANCldlIGNvbnNpZGVyIG9ubHkgc2FtcGxlcyBpbiB0aGUgb21pY3MgZGF0YSBpbiBgYGBjb21wbGV0ZWBgYCBmb3Igd2hpY2ggYWxzbyBzdWJ0eXBlIGRhdGEgaXMgcHJlc2VudCBpbiBgYGBzdWJ0eXBlc2BgYA0KYGBge3J9DQpyb3duYW1lcyhzdWJ0eXBlcykgPC0gc3Vic3RyKHN1YnR5cGVzJHBhbi5zYW1wbGVzSUQsIDEsIDEyKTsNCmZvciAoaSBpbiAxOmxlbmd0aChjb21wbGV0ZSkpDQogIGNvbXBsZXRlW1tpXV0gPC0gY29tcGxldGVbW2ldXVtyb3duYW1lcyhzdWJ0eXBlcyksXQ0KIyBQcmludCBudW1iZXIgb2Ygc2FtcGxlcyBmb3IgZWFjaCBzdWJ0eXBlOg0KdGFibGUoc3VidHlwZXMkU3VidHlwZV9JbnRlZ3JhdGl2ZSk7DQpgYGANCiMjIENoZWNrIHN1YnR5cGUgJiBvbWljcyBkYXRhIG9yZGVyDQpgYGB7cn0NCmNvdW50IDwtIDANCmZvcihpIGluIDE6bGVuZ3RoKHJvd25hbWVzKHN1YnR5cGVzKSkpew0KICBpZihyb3duYW1lcyhzdWJ0eXBlcylbaV0gIT0gcm93bmFtZXMoY29tcGxldGVbWzFdXSlbaV0pDQogICAgIGNvdW50IDwtIGNvdW50ICsgMQ0KfQ0KY291bnQNCmBgYA0KQWxsIHBhdGllbnRzL3NhbXBsZXMgYXJlIGluIHRoZSBzYW1lIG9yZGVyIGluIGJvdGggdGhlIGRhdGFzZXRzLg0KIyBNdWx0aS1vbWljcyBkYXRhIGludGVncmF0aW9uDQpTaW1pbGFyaXR5IG1hdHJpY2VzIGZvciBlYWNoIGRhdGEgc291cmNlIHVzaW5nIGV4cG9uZW50aWFsIGV1Y2xpZGlhbiBkaXN0YW5jZSAoYWZmaW5pdHkgbWF0cml4KS4NCmBgYHtyfQ0KV19saXN0IDwtIGxpc3QoKTsNCmZvcihpIGluIDE6bGVuZ3RoKGNvbXBsZXRlKSl7DQogICAgRGlzdCA8LSAoZGlzdDIoYXMubWF0cml4KGNvbXBsZXRlW1tpXV0pLCBhcy5tYXRyaXgoY29tcGxldGVbW2ldXSkpKV4oMS8yKQ0KICAgIFdfbGlzdFtbaV1dIDwtIGFmZmluaXR5TWF0cml4KERpc3QpDQp9DQpgYGANCiMjIEludGVncmF0aW9uIHRocm91Z2ggU05GDQpJbnRlZ3JhdGlvbiBvZiB0aGUgbWF0cmljZXMgdXNpbmcgU2ltaWxhcml0eSBOZXR3b3JrIEZ1c2lvbg0KKl90XyBudW1iZXIgb2YgaXRlcmF0aW9ucw0KKl9LXyBudW1iZXIgb2YgbmVpZ2hib3VycyB0byBjb25zaWRlciB0byBjb21wdXRlIGxvY2FsIHNpbWlsYXJpdHkgbWF0cml4DQoNCmBgYHtyfQ0KV19pbnRfU05GIDwtIFNORihXX2xpc3QsIEs9MjAsIHQ9MjApOw0KYGBgDQojIyBJbnRlZ3JhdGlvbiB0aHJvdWdoIGF2ZXJhZ2UNCkludGVncmF0aW9uIHRocm91Z2ggYXZlcmFnZSBvZiBtYXRyaWNlcw0KYGBge3J9DQpXX2ludF9tZWFuIDwtIFJlZHVjZSgnKycsIFdfbGlzdCkvbGVuZ3RoKFdfbGlzdCkNCmBgYA0KYGBge3J9DQpmb3IgKGkgaW4gMTpsZW5ndGgoV19saXN0KSkNCiAgICBwbG90KFdfbGlzdFtbaV1dLHhsaW09YygwLDAuMDEpLHlsaW09YygwLDAuMDEpKQ0KYGBgDQoNCmBgYHtyfQ0KcGxvdChXX2ludF9tZWFuLHhsaW09YygwLDAuMDEpLHlsaW09YygwLDAuMDEpKQ0KYGBgDQpgYGB7cn0NCnBsb3QoV19pbnRfU05GLHhsaW09YygwLDAuMDEpLHlsaW09YygwLDAuMDEpKQ0KYGBgDQojIERpc2Vhc2Ugc3VidHlwZSBkaXNjb3Zlcnkgd2l0aCBQQU0NCk51bWJlciBvZiBjbHVzdGVycy4NCmBgYHtyfQ0KayA8LSBsZW5ndGgodW5pcXVlKHN1YnR5cGVzJFN1YnR5cGVfSW50ZWdyYXRpdmUpKTsNCmBgYA0KIyMgRWFjaCBkYXRhIHNvdXJjZQ0KQ29udmVydCBzaW1pbGFyaXR5IG1hdHJpeCBpbnRvIGEgZGlzdGFuY2UgbWF0cml4LiBUaGUgc2ltaWxhcml0aWVzIGFyZSBub3JtYWxpemVkIGluIHRoZSByYW5nZSAmXGxlZnRbMCwgMVxyaWdodF0kIHVzaW5nIG1pbi1tYXggbm9ybWFsaXphdGlvbiBiZWZvcmUgY29udmVyc2lvbiBpbnRvIGRpc3RhbmNlcy4NCmBgYHtyfQ0KZGlzdCA8LSBsaXN0KCkNCkQgPC0gbGlzdCgpDQpmb3IgKGkgaW4gMTpsZW5ndGgoKFdfbGlzdCkpKXsNCiAgZGlzdFtbaV1dIDwtIDEgLSBOZXRQcmVQcm9jOjpNYXguTWluLm5vcm0oV19saXN0W1tpXV0pDQogIERbW2ldXSA8LSBhcy5kaXN0KGRpc3RbW2ldXSkNCn0NCmZvciAoaSBpbiAxOmxlbmd0aCgoV19saXN0KSkpDQogIHBhbS5yZXMgPC0gcGFtKERbW2ldXSwgaz1rKQ0KYGBgDQojIyBJbnRlZ3JhdGVkIGRhdGEgdGhyb3VnaCBtZWFuDQpgYGB7cn0NCmRpc3RfbWVhbiA8LSAxIC0gTmV0UHJlUHJvYzo6TWF4Lk1pbi5ub3JtKFdfaW50X21lYW4pOw0KRF9tZWFuIDwtIGFzLmRpc3QoZGlzdF9tZWFuKTsgDQoNCnBhbS5yZXMgPC0gcGFtKERfbWVhbiwgaz1rKTsNCmBgYA0KIyMgSW50ZWdyYXRlZCBkYXRhIHRocm91Z2ggU05GDQpgYGB7cn0NCmRpc3RfU05GIDwtIDEgLSBOZXRQcmVQcm9jOjpNYXguTWluLm5vcm0oV19pbnRfU05GKTsNCkRfU05GIDwtIGFzLmRpc3QoZGlzdF9TTkYpOyANCg0KIyBBcHBseSBjbHVzdGVyaW5nIGFsZ29yaXRobXMgb24gaW50ZWdyYXRlZCBtYXRyaXg6DQpwYW0ucmVzIDwtIHBhbShEX1NORiwgaz1rKTsNCmBgYA0KI0Rpc2Vhc2Ugc3VidHlwZSBkaXNjb3Zlcnkgd2l0aCBzcGVjdHJhbCBjbHVzdGVyaW5nDQooQ29uc2lkZXIgZGlzdGFuY2UgbWF0cml4IGNhbGN1bGF0ZWQgYWJvdmUpDQojIyBJbnRlZ3JhdGVkIGRhdGEgdGhyb3VnaCBTTkYNCmBgYHtyfQ0KayA8LSBsZW5ndGgodW5pcXVlKHN1YnR5cGVzJFN1YnR5cGVfSW50ZWdyYXRpdmUpKTsNCnNjLnJlcyA8LSBTTkZ0b29sOjpzcGVjdHJhbENsdXN0ZXJpbmcoV19pbnRfU05GLCBLPWspDQojdG8gaGF2ZSB1bmlmb3JtIHR5cGUNCnBhbS5zYy5yZXMgPC0gcGFtKHNjLnJlcyxrPWspDQpgYGANCg0KDQpgYGB7cn0NCnNlc3Npb25JbmZvKCkNCmBgYA0KDQo=